package com.hanxiaozhang.greedy;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 〈一句话功能简述〉<br>
 * 〈最优会议安排〉
 *
 * @author hanxinghua
 * @create 2021/9/22
 * @since 1.0.0
 */
public class BestArrange {


    /**
     * 题目：
     * 一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。
     * 给你每一个项目开始的时间和结束的时间。你来安排宣讲的日程，
     * 要求会议室进行的宣讲的场次最多。返回最多的宣讲场次。
     *
     * @param args
     */
    public static void main(String[] args) {
        int programSize = 12;
        int timeMax = 20;
        int timeTimes = 1000000;
        for (int i = 0; i < timeTimes; i++) {
            Meeting[] meetings = generateMeetings(programSize, timeMax);
            if (bestArrange1(meetings) != bestArrange2(meetings)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("finish!");

    }

    /**
     * 暴力递归
     *
     * @param meetings
     * @return
     */
    public static int bestArrange1(Meeting[] meetings) {
        if (meetings == null || meetings.length == 0) {
            return -1;
        }
        return process(meetings, 0, 0);
    }


    /**
     * @param meetings   剩余会议
     * @param arrangeNum 已经安排会议数量
     * @param curTime    当前的时间点
     * @return
     */
    private static int process(Meeting[] meetings, int arrangeNum, int curTime) {
        // 剩余可以安排会议数量为0，返回arrangeNum
        if (meetings.length == 0) {
            return arrangeNum;
        }
        int max = arrangeNum;
        int length = meetings.length;
        for (int i = 0; i < length; i++) {
            if (meetings[i].start >= curTime) {
                Meeting[] next = copyButExcept(meetings, i);
                max = Math.max(max, process(next, arrangeNum + 1, meetings[i].end));
            }
        }
        return max;
    }

    /**
     * 拷贝删除某个元素的数组
     *
     * @param meetings
     * @param i
     * @return
     */
    private static Meeting[] copyButExcept(Meeting[] meetings, int i) {
        Meeting[] ans = new Meeting[meetings.length - 1];
        int index = 0;
        for (int k = 0; k < meetings.length; k++) {
            if (k != i) {
                ans[index++] = meetings[k];
            }
        }
        return ans;
    }


    /**
     * 贪心算法：
     * 贪心策略A：
     * 按开始时间比较 --> 可以找出反例，错误
     * ... ...
     * 贪心策略D：
     * 按结束时间比较 --> 正确
     * Tips：
     * 1. 对于能举出反例的策略直接跳过，不能举出反例的策略要证明有效性
     * 2. 用解法X和对数器，用实验的方式得知哪个贪心策略正确，不要去纠结贪心策略的证明
     * 3. 对于贪心算法的学习主要以增加阅历和经验为主
     *
     *
     * @param meetings
     * @return
     */
    public static int bestArrange2(Meeting[] meetings) {
        // 按结束时间大小排序
        Arrays.sort(meetings, new MeetingComparator());
        // 当前时间点
        int curTime = 0;
        // 安排结果数
        int result = 0;
        for (int i = 0; i < meetings.length; i++) {
            // 当前时间点小于会议开始时间，可以安排
            if (curTime <= meetings[i].start) {
                result++;
                curTime = meetings[i].end;
            }
        }
        return result;
    }

    /**
     * 比较器
     */
    public static class MeetingComparator implements Comparator<Meeting> {
        @Override
        public int compare(Meeting o1, Meeting o2) {
            return o1.end - o2.end;
        }
    }


    /**
     * 生成会议
     *
     * @param programSize
     * @param timeMax
     * @return
     */
    private static Meeting[] generateMeetings(int programSize, int timeMax) {
        Meeting[] ans = new Meeting[(int) (Math.random() * (programSize + 1))];
        for (int i = 0; i < ans.length; i++) {
            int r1 = (int) (Math.random() * (timeMax + 1));
            int r2 = (int) (Math.random() * (timeMax + 1));
            if (r1 == r2) {
                ans[i] = new Meeting(r1, r1 + 1);
            } else {
                ans[i] = new Meeting(Math.min(r1, r2), Math.max(r1, r2));
            }
        }
        return ans;
    }

    /**
     * 会议实体
     */
    public static class Meeting {
        public int start;
        public int end;

        public Meeting(int start, int end) {
            this.start = start;
            this.end = end;
        }

    }

}
